package com.congee02;

import java.util.Arrays;

public class LongestPalindrome_Cache_TL {

    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }

        for (int[][] e : cache) {
            for (int[] c : e) {
                Arrays.fill(c, -1);
            }
        }

        char[] str = manacher(s);

        int[] range = process(str, 0, str.length - 1);

        System.out.println(Arrays.toString(range));
        System.out.println(String.valueOf(str));

        StringBuilder sb = new StringBuilder((range[1] - range[0]) / 2 + 1);
        for (int i = range[0] ; i <= range[1] ; i ++ ) {
            if (str[i] != '#') {
                sb.append(str[i]);
            }
        }

        return sb.toString();
    }

    private int[][][] cache = new int[1001][1001][2];
    private int[] process(char[] str, int st, int ed) {
        if (st == ed) {
            return new int[]{st, st};
        }
        if (st > ed) {
            return new int[]{0, Integer.MIN_VALUE};
        }

        if (cache[st][ed][0] == -1) {
            cache[st][ed] = doProcess(str, st, ed);
        }
        return cache[st][ed];
    }

    private int[] doProcess(char[] str, int st, int ed) {
        if (str[st] == str[ed]) {
            int[] p = process(str, st + 1, ed - 1);
            if (p[0] == st + 1 && p[1] == ed - 1) {
                return new int[]{st, ed};
            }
        }

        int[] p1 = process(str, st + 1, ed);
        int[] p2 = process(str, st, ed - 1);

        return max(p1, p2);
    }

    private int[] max(int[] r1, int[] r2) {
        int d1 = r1[1] - r1[0];
        int d2 = r2[1] - r2[0];
        return d1 > d2 ? r1 : r2;
    }


    private static final char M = '#';
    private char[] manacher(String s) {
        char[] ans = new char[s.length() * 2 + 1];

        int k = 0;
        ans[k ++] = M;

        char[] cs = s.toCharArray();

        for (char x : cs) {
            ans[k ++] = x;
            ans[k ++] = M;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new LongestPalindrome_Cache_TL().longestPalindrome("babad"));
    }

}
